49. 字母异位词分组

49. 字母异位词分组

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>()

  for (const str of strs) {
    // 将字符串排序作为 key
    const key = str.split('').sort().join('')
    if (!map.has(key)) {
      map.set(key, [])
    }
    map.get(key)!.push(str)
  }

  return Array.from(map.values())
}

问题本质

字母异位词分组的核心不在于「如何分组」，而在于为等价类找一个稳定的表示。

两个字符串互为字母异位词 ⟺ 它们的字符构成完全相同，只是排列不同。这意味着任何能消除排列差异的表示，都可以作为等价类的标识符。排序恰好提供了这样一种表示——无论原字符串的字符顺序如何，排序后的结果都是相同的。

所以这题本质上是一个等价类分组问题，用哈希表把同一等价类的元素收集到一起。

复杂度与替代方案

排序方案的时间复杂度是 O(N·K log K)，其中 N 是字符串数量，K 是最大字符串长度。瓶颈在于对每个字符串排序。

另一种常见做法是用字符频次计数作为 key，比如 "a2b1c3" 这种编码，可以将单个字符串的处理降到 O(K)，但 key 的构造更繁琐，而且只有在小字符集（如 26 个小写字母）时更有优势。排序方案的特点是简洁、通用，不受字符集限制。

实际场景中 K 通常不会很大，排序的开销可以接受。

边界注意

• 空字符串 "" 排序后仍是 ""，它可以作为合法的 key
• 单个字符串的情况，结果应是 [["abc"]] 而非 ["abc"]
• Map 的 values 迭代顺序在 ES6 中是插入顺序，但此处不依赖顺序